{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第一章 绪论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 1.1 表1. 1中若只包含编号为1和4的两个样例，试给出相应的版本空间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "    编号  色泽 根蒂 敲声 好瓜\n",
    "      1   青绿 蜷缩 浊响  是 \n",
    "      4   乌黑 稍蜷 沉闷  否 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "**假设空间**：每种属性所有可能取值的组合\n",
    "\n",
    "假设n个属性，每个属性有$t_{i}$个取值，\\*为任意取值，假设空间大小：$H = \\sum_{i=1}^{n}({t_i}+1)$\n",
    "\n",
    "**版本空间**：与训练集一致的假设集合空间\n",
    "\n",
    "即假设空间中 正例 + 正例一般情形 - 负例一般情形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "版本空间：\n",
    "\n",
    "(色泽=青绿;根蒂=蜷缩;敲声=浊响)\n",
    "\n",
    "(色泽=青绿;根蒂=\\*;敲声=\\*)\n",
    "\n",
    "(色泽=\\*;根蒂=蜷缩;敲声=\\*)\n",
    "\n",
    "(色泽=\\*;根蒂=\\*;敲声=浊响)\n",
    "\n",
    "(色泽=青绿;根蒂=蜷缩;敲声=\\*)\n",
    "\n",
    "(色泽=\\*;根蒂=蜷缩;敲声=浊响)\n",
    "\n",
    "(色泽=青绿;根蒂=\\*;敲声=浊响)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 1.2 若使用最多包含k个合取式的析合范式来表达表1. 1西瓜分类问题的假设空间，试估算共有多少种可能的假设。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "假设不考虑空集\n",
    "\n",
    "不考虑冗余：$\\sum_{k}C_{48}^{k} = 2^{48}$\n",
    "\n",
    "考虑冗余："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第二章 模型评估与选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.1 数据集包含 1000 个样本，其中 500 个正例、 500 个反例，将其划分为包含 70% 样本的训练集和 30% 样本的测试集用于留出法评估，试估算共有多少种划分方式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "留出法等价于分层抽样。\n",
    "\n",
    "7：3，故从500正例中抽取350个，从500反例中抽取350个，共$(C_{500}^{350})^{2}$种划分方式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.2 数据集包含 100 个样本，其中正、反例各一半，假定学习算法所产生的模型是将新样本预测为训练样本数较多的类别(训练样本数相同时进行随机猜测)，试给出用 10 折交叉验证法和留一法分别对错误率进行评估所得的结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "10拆交叉验证法：划分10组，每组10个，分层抽样。其中每组训练集测试集均为5个正例，5个反例，进行随机猜测，\n",
    "\n",
    "故$E(y)=\\frac{\\sum_{i=1}^{10}k_i}{10}=\\frac{10 \\times \\frac{1}{2}}{10}=\\frac{1}{2}$.\n",
    "\n",
    "留一法：划分100组，每组1个。若留一正例为测试集，剩下反例多正例一个，预测结果必为反例；反之留一反例，则预测结果必为正例，\n",
    "\n",
    "故预测错误率为1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.3 若学习器A的F1值比学习器B高试析A的BEP值是否也比B高。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "参考：\n",
    "\n",
    "[机器学习中的指标F1](https://blog.csdn.net/qwer7512090/article/details/93743693)\n",
    "\n",
    "[机器学习中的F1-score](https://www.cnblogs.com/yucen/p/9912063.html)\n",
    "\n",
    "[机器学习系列（三十）——F1 Score与Precision-Recall的平衡](https://www.jianshu.com/p/5285c938b94a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "不一定。\n",
    "\n",
    "若理解$F_1$的值为学习器O训练k次的$F_1$的算式平均值，则无法由$\\sum_{i}F_1i(A) > \\sum_{i}F_1i(B)$推出$BEP(A)$与$BEP(B)$的关系。\n",
    "\n",
    "若理解为单次训练的$F_1$的值，考虑$F_1$值最大的情形，指标$F_1$的值为$P$和$R$的调和平均数，故在$P=R$时$F_1$取最大值。\n",
    "\n",
    "此时，因为$F_1(A)>F_1(B)$，所以$\\frac{2}{BEP(A)}<\\frac{2}{BEP(B)}$，即$BEP(A)>BEP(B)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.4 试述真正例率(TPR) 、假正例率(FPR) 与查准率(P) 、查全率(R) 之间的联系。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "$P = \\frac{TP}{TP + FP}$  查准率，即预测结果为正例的样本中真正例的比率。\n",
    "\n",
    "$R = \\frac{TP}{TP + FN}$  查全率，即真实结果为正例的样本中真正例的比率。\n",
    "\n",
    "$TPR = \\frac{TP}{TP + FN}$  真正例率，即真实结果为正例的样本中真正例的比率。\n",
    "\n",
    "$FPR = \\frac{FP}{TN + FP}$  假正例率，即真实结果为反例的样本中假正例的比率。\n",
    "\n",
    "显然，查全率等价于真正例率，且$\\frac{TP}{TPR} + \\frac{FP}{FPR} = 样本总数$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.5 试证明式(2.22) $AUC = 1 - l_{rank}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "参考：\n",
    "\n",
    "[机器学习(周志华) 参考答案 第二章 模型评估与选择](https://blog.csdn.net/icefire_tyh/article/details/52065867)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "$AUC = \\frac{1}{2}\\sum_{i=1}^{m-1}(x_{i+1} - x_i) \\cdot (y_i + y_{i+1})$\n",
    "\n",
    "$l_{rank} = \\frac{1}{m^+ \\cdot m^-}\\sum_{x \\in D^+}\\sum_{x \\in D^-}(I(f(x^+)<f(x^-)) + \\frac{1}{2}I(f(x^+)=f(x^-)))$\n",
    "\n",
    "令横坐标为**当前反例个数**，纵坐标为**当前正例个数**，AUC可以理解为，设前一样本坐标$(x,y)$，若样本排序中当前为正例，则当前坐标为$(x,y+1)$；若样本排序中当前为反例，则当前坐标为$(x+1,y)$或$(x+\\frac{1}{2},y+\\frac{1}{2})$。横、纵坐标分别缩小$m^-、m^+$倍，即作归一化处理后，横坐标就是FPR，纵坐标就是TPR.\n",
    "\n",
    "故$AUC = \\frac{1}{m^+ \\cdot m^-}\\sum_{x \\in D^+}\\sum_{x \\in D^-}(I(f(x^+)>f(x^-)) + \\frac{1}{2}I(f(x^+)=f(x^-))$，显然$AUC + l_{rank} = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.6 试述错误率与 ROC 曲线的联系。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "错误率越低，ROC曲线越陡峭（贴近TPR轴）；错误率越高，ROC曲线越平缓（贴近FPR轴）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.7 试证明任意一条 ROC 曲线都有一条代价曲线与之对应，反之亦然。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "横轴为$P(+)cost = \\frac{p \\times cost_{01}}{p \\times cost_{01} + (1 - p) \\times cost_{10}}$\n",
    "\n",
    "纵轴为$cost_{norm} = \\frac{FNR \\times p \\times cost_{01} + FPR \\times (1 - p) \\times cost_{10}}{p \\times cost_{01} + (1 - p) \\times cost_{10}}$\n",
    "\n",
    "任取一条ROC曲线，即$\\{FPR\\} \\rightarrow \\{TPR\\}$，对固定的$(FPR,TPR)$投到代价平面的$(0,FPR)$和$(1,1-TPR)$上连成一条线段，对ROC曲线上所有的点作此投影，取线段集合$\\{y = (FNR - FPR)x + FPR\\}$公共下界，即为代价曲线。故任意一条ROC曲线有一条代价曲线与之对应。\n",
    "\n",
    "反之，求偏导$\\frac{\\partial cost_{norm}}{\\partial P(+)cost} = FNR - FPR$，令偏导等于0，则每一处切点对应一条线段，交$x = 0$，$x = 1$两点即为$(0,FPR)$，$(1,FNR)$，对应ROC曲线上一点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.8 Min-max规范化和z-score规范化是两种常用的规范化方法。令$x,x'$分别表示变量在规范化前后的取值，相应的$x_{min},x_{max}$即表示规范化前的最小值和最大值,$x'_{min},x'_{max}$表示规范化后的最小值和最大值，${\\bar x},\\sigma$分别表示规范化前的均值和标准差，则 min-max 规范化、 z-score 规范化分别如式(2 .43) (2 .44) 所示。试析二者的优缺点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "$x' = \\frac{x - x_{min}}{x_{max - x_{min}}}$   (2.43)\n",
    "\n",
    "$x' = \\frac{x - {\\bar x}}{\\sigma}$   (2.44)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "参考：\n",
    "\n",
    "[真的明白数据归一化(MinMaxScaler)和数据标准化(StandardScaler)吗？](https://blog.csdn.net/wuzhongqiang/article/details/103764412)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "两者都可以使数据无量纲化。\n",
    "\n",
    "z-score规范化后x均值为0，方差为1，取值范围[-1,1]，不改变样本的分布。\n",
    "\n",
    "min-max规范化后取值范围为[0,1]，样本的分布改变，使得扁平化的数据变成类圆形，提高迭代收敛速度和精度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.9 试述 χ2 检验过程."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## 2.10* 试述在Friedman 检验中使用式(2.34) (2.35) 的区别."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
